package com.labuladong;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 项目名称: java_algorithm
 * @ClassName TreeMostSmallDegree
 * @Description 二叉树的最小高度(BFS为一层一层遍历，DFS为一条一条遍历，使用队列链表结构while遍历)
 * @Author huipanxing huipanxing@chinasofti.com   @Date 2022/6/23 15:38
 */
public class TreeMostSmallDegree {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        treeNode.setTreeValue(1);
        treeNode.setLeftNode(new TreeNode() {{
            setTreeValue(2);
        }});

        treeNode.setRightNode(new TreeNode() {{
            setLeftNode(new TreeNode() {{
                setTreeValue(3);
            }});
            setRightNode(new TreeNode() {{
                setTreeValue(4);
            }});
        }});

        int result = minDepth(treeNode);
        System.out.println(result);
    }

    public static int minDepth(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        int length = 1;
        queue.offer(treeNode);

        while (!queue.isEmpty()) {
            int size = queue.size();
            //必须一层一层遍历
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (null == node.getLeftNode() && null == node.getRightNode()) {
                    return length;
                }
                if (null!=node.getLeftNode()){
                    queue.offer(node.getLeftNode());
                }
                if (null!=node.getRightNode()){
                    queue.offer(node.getRightNode());
                }
            }
            length++;
        }
        return length;
    }
}
